package codingforgreat.lchot150;

import java.util.List;

public class Lc139 {
    public class Node{
        public boolean end;
        public Node[] nexts;
        public Node(){
            end = false;
            nexts = new Node[26];
        }

    }
    public boolean wordBreak(String s, List<String> wordDict) {
        Node root = new Node();
        for (String str : wordDict) {
            char[] chs = str.toCharArray();
            Node node = root;
            int index = 0;
            for (int i = 0; i < chs.length; i++) {
                index = chs[i] - 'a';
                if (node.nexts[index] == null) {
                    node.nexts[index] = new Node();
                }
                node = node.nexts[index];
            }
            node.end = true;
        }
        char[] str = s.toCharArray();
        Info[] dp = new Info[str.length + 3];
        return process(str,0,root,dp);
    }
    public class Info{
        public boolean res;
        public Info(boolean f){
            res = f;
        }
    }
    public boolean process(char[] s,int index,Node root,Info[] dp){
        if(dp[index] != null){
            return dp[index].res;
        }
        if(index >= s.length){
            dp[index] = new Info(true);
            return true;
        }
        boolean res = false;
        Node node = root;
        for(int i = index;((i <= s.length) && (node != null));i++){
            if(node.end == true){
                res |= process(s,i,root,dp);
            }
            if((i == s.length) && (node.end == true)){
                dp[index] = new Info(true);
                return true;
            }else if(i == s.length){
                dp[index] = new Info(res | false);
                return false | res;
            }
            int n = s[i] - 'a';
            node = node.nexts[n];
        }
        dp[index] = new Info(res);
        return res;
    }

    public boolean wordBreak1(String s, List<String> wordDict) {
        Node root = new Node();
        for (String str : wordDict) {
            char[] chs = str.toCharArray();
            Node node = root;
            int index = 0;
            for (int i = 0; i < chs.length; i++) {
                index = chs[i] - 'a';
                if (node.nexts[index] == null) {
                    node.nexts[index] = new Node();
                }
                node = node.nexts[index];
            }
            node.end = true;
        }
        char[] str = s.toCharArray();
        int N = str.length;
        boolean[] dp = new boolean[N + 1];
        dp[N] = true; // dp[i]  word[i.....] 能不能被分解
        // dp[N] word[N...]  -> ""  能不能够被分解
        // dp[i] ... dp[i+1....]
        for (int i = N - 1; i >= 0; i--) {
            // i
            // word[i....] 能不能够被分解
            // i..i    i+1....
            // i..i+1  i+2...
            Node cur = root;
            for (int end = i; end < N; end++) {
                cur = cur.nexts[str[end] - 'a'];
                if (cur == null) {
                    break;
                }
                // 有路！
                if (cur.end) {
                    // i...end 真的是一个有效的前缀串  end+1....  能不能被分解
                    dp[i] |= dp[end + 1];
                }
                if (dp[i]) {
                    break;
                }
            }
        }
        return dp[0];

//        boolean res = false;
//        Node node = root;
//        for(int i = index;((i <= s.length) && (node != null));i++){
//            if(node.end == true){
//                res |= process(s,i,root,dp);
//            }
//            if((i == s.length) && (node.end == true)){
//                dp[index] = new Info(true);
//                return true;
//            }else if(i == s.length){
//                dp[index] = new Info(res | false);
//                return false | res;
//            }
//            int n = s[i] - 'a';
//            node = node.nexts[n];
//        }
//        dp[index] = new Info(res);
//        return res;

    }
}
